Batch 3 - Class 143 - Induction III, Visualization

• (Cornell) Two people have two consecutive natural numbers pasted on their heads, which they can't see but the other person can see. First person starts by asking the other if she knows what her number is. If she says yes, game ends. If she says no, she asks the first person if he knows his number. And so on. Does the game ever end? Sometimes? Never? Always?
• Let kids think -intuitively, the answer is that the game doesn't end
• Ask someone what is your name repeatedly to reinforce this false intuition - it seems that asking the same question again and again doesn't help
• What if the second person sees a number 1 on first person's forehead? Oh, so it does finish in some cases? Which ones?
• What if first person sees a number "2" on second person's forehead? What can he reason by hearing a "no" from the second person? What if there is a "4" on one person's head?
• Can we form an induction hypothesis?
• The game ends in at most 2n steps, if n is the lower of the two numbers
• Note that in some cases, forming the hypothesis can be challenging
• Base case is already proven
• Prove the induction step

• Lets go back to our problem of finding number of squares on a n x n grid. We had to total 1+2+3+4+...+n+(n-1)...1   - Can you do this visually?
• Answer: Sum of diagonals of a (n) x (n) grid, and hence n^2
• Can you now find 1+2+3+4+...n using this?
• Answer: Just add n to both sides of initial equation, and divide by 2, to get n(n+1)/2
• Can you solve for 1+2+3..n using induction?
• Can you see 1+3+5+7+9 in a 5x5 grid?
• Answer: Consider the "L" shapes. The total must again be n^2
• How about sum of first 5 even numbers?
• Answer: Just add a row to our grid. Its n^2+n
• Note that if we halve this, its just sum of first 5 numbers, and its (n^2+n)/2
• What would be the sum of first two odd numbers divided by sum of next two odd numbers? How about first three to next three? Four? Is there a pattern? Can you visualize that on a grid?

• Difference relative to deduction? From specific to general.
• Steps in Induction proofs
• The Hypothesis
• Trick to forming a hypothesis - solve for smallest 4-5 cases - try to spot the pattern
• Basis Step
• Induction Step - Note that Induction step only assumes that the hypothesis holds upto "n", and not in general - that is what we are trying to prove.
• Caution - Wrong Proofs using Induction - let the kids spot the errors
• (Decade - 6 - Section 6 - 1) All natural numbers are even - Assume that any natural number up to n is even. We want to prove that n+1 is also even. Since n+1=n-1+2. What's wrong?
• We have not proven our base hypothesis. 1 is odd
• (Decade - 6 - Section 6 - 2) All dogs are the same color - Basis step: 1 dog is obviously of the same color. Take n+1 dogs. If all sets of n dogs are the same color, then take a dog A out and rest must be of same color. Now take a dog B out and rest must be of same color. In the dogs left in both cases, there is a dog C, which is common. And hence the two sets need to be of same color. Hence proved.
• We have assumed at least three dogs, so we must prove for 2 dogs, not just for one. Our induction step doesn't hold for 2 dogs.

• (MC - 9 - 37) A bank has unlimited supply of Rs 3 and Rs 5 notes. Prove that it can pay out any amount above Rs 8.